The present invention relates to a method of securely implementing a cryptography algorithm in an electronic component, and more particularly to a method of securely implementing a cryptography algorithm of the Rivest-Shamir-Adleman (RSA) type.
The invention also relates to the corresponding electronic component.
Such components are, in particular used in applications in which access to services or to data is stringently controlled.
They have a “software” architecture, i.e. a programmable architecture, formed around a microprocessor and around memories, including a non-volatile memory of the Electrically Erasable Programmable Read-Only Memory (EEPROM) type which contains one or more secret numbers. The architecture is a non-specialist architecture suitable for executing any algorithm.
Such components are used in computer systems, on-board or otherwise. They are used, in particular, in smart cards, for certain applications thereof. For example, such uses are applications for access to certain databanks, banking applications, remote payment applications, e.g. for television purchases, for gasoline purchases, or for payment of highway tolls.
Such components or cards thus implement a cryptography algorithm for encrypting transmitted data and/or for decrypting received data, or for authenticating or digitally signing a message.
On the basis of such a message applied as input into the card by a host system (server, automatic teller machine, etc.) and on the basis of secret numbers contained in the card, the card returns the message as encrypted, authenticated, or signed to the host system, thereby enabling the host system to authenticate the component or the card, and to exchange data, etc.
The characteristics of the cryptography algorithm can be known: computations performed; parameters used. The only unknown quantity is the secret number(s). The entire security of such cryptography algorithms relies on that/those secret number(s) contained in the card and unknown to the world outside the card. The secret number(s) cannot be deduced merely by knowledge of the message applied as input and of the encrypted message delivered in return.
Unfortunately, it has appeared that external attacks based on physical magnitudes measurable from the outside of the component while said component is running the cryptography algorithm make it possible for ill-intentioned people to find the secret number(s) contained in the card. Such attacks are known as “side channel attacks”. Among such side channel attacks, there are Single Power Analysis (SPA) attacks based on one measurement or a few measurements, and Differential Power Analysis (DPA) attacks based on statistical analyses resulting from many measurements. The principle of such side channel attacks is based, for example, on the fact that the current consumption of the microprocessor executing instructions varies as a function of the instruction or of the data being handled.
There also exists a type of attack known as a “fault attack”. In that type of attack, the attacker injects any fault while the cryptography algorithm is being computed, with the aim of using the presence of the fault to extract secret information.
The fault can also come from a computation error due to the hardware implementing the cryptography algorithm. However, in both cases, it is considered that a fault attack has occurred.
The various types of attack are possible in particular with public-key cryptography algorithms such as, for example, the RSA algorithm (named after its authors Rivest, Shamir, and Adleman) which is the algorithm that is in most widespread use in this field of application, and to which the present invention is more particularly applicable.
The main characteristics of the RSA public-key cryptographic system are recalled briefly below.
The first public-key encryption and signature scheme was developed in 1977 by Rivest, Shamir, and Adleman, who invented the RSA cryptographic system. The security of RSA is based on the difficulty of factoring a large number that is the product of two prime numbers. That system is the most widely used public-key cryptographic system. It can be used as an encryption method or as a signature method.
The principle of the RSA cryptographic system is as follows. It consists firstly in generating the pair of RSA keys.
Thus, each user creates an RSA public key and a corresponding private key, using the following 5-step method:
1) Generate two distinct prime numbers p and q;
2) Compute n=pq and Φ(n)=(p−1)(q−1), where Φ is called the Euler totient function or the Euler phi-function;
3) Select an integer e, 1<e<Φ(n), such that pgcd(e,Φ(n))=1, randomly or on the choice of the user who could thus choose e to be small such that e=216+1 or e=3 or e=17;
4) Compute the unique integer d, 1<d<Φ(n), such that: e·d=1 modulo Φ(n); (1)
5) The public key is (n,e); the private key is d or (d,p,q).
The integers e and d are called respectively the “public exponent” and the “private exponent”. The integer n is called the “RSA modulus”.
Once the public and private parameters are defined, given x, with 0<x<n, the public operation on x which can, for example, be the encryption of the message x, consists in computing: y=xe modulo n (2) In which case, the corresponding private operation is the operation of decrypting the encrypted message y, and consists in computing:Yd modulo n  (3)
The public operation on x can also be verification of the signature x, and then consist in computing:y=xe modulo n  (2)
The corresponding private operation is then generation of a signature x on the basis of the previously encoded message y by applying a hash function or “padding” function μ, and consists in computing:Yd modulo n  (3)
Where x=yd modulo n since e·d=1 modulo Φ (n) Another mode of operation known as the Chinese Remainder Theorem (CRT) mode is presented below. It is four times faster than the mode of operation of the standard RSA algorithm. In the CRT mode, the modulo n computations are not performed directly, but rather the modulo p and modulo q computations are performed first.
The public parameters are (n, e) but, in the CRT mode, the private parameters are (p, q, d) or (p, q, dp, dq, iq), where
dp=d modulo (p−1), dq=d modulo (q−1) and iq=q−1 modulo p
By relationship (1), the following are obtained:edp=1 modulo (p−1)andedq=1 modulo (q−1)  (4)
The public operation is performed in the same manner as for the standard operating mode. In contrast, for the private operation, the following are computed first:
xp=ydp modulo p and xq=ydq modulo q
Then, by applying the Chinese Remainder Theorem, x=yd modulo n is obtained by:x=CRT(xp, xq)=xq+q[iq(xp−xq) modulop]  (5)
An important aspect of the field of public-key cryptography using the RSA encryption scheme thus consists in making implementation of the RSA algorithms secure against the various possible types of attack mentioned above, in particular side channel attacks such as DPA and SPA attacks, as well as “fault” attacks in which the attacker, by using any method, injects a fault during the computation of a private operation of the RSA algorithm with the aim of obtaining a corrupted value from which it is possible, in certain cases, to deduce certain items of secret data.
In the state of the art, certain countermeasure methods have been devised for parrying the various types of attack.
In particular, one possible countermeasure for parrying DPA (and SPA) type attacks against RSA in standard mode consists in making the private operation (signature or decryption) of the RSA random by inserting a random value into the computation.
Thus, one countermeasure method of that type consists in computing the private operation in standard mode (3) x=yd modulo n in the following manner:
x=yd−r·yr modulo n, where r is a random integer. However the drawback with that countermeasure method is that the computing time is doubled.
Another countermeasure method of that type for parrying DPA (and SPA) attacks against RSA in standard mode consists in computing the private operation (3) x=yd modulo n in the following manner:
x=y(d+r·Φ(n)) modulo n, where r is a random integer. However the drawback with that countermeasure method is that it requires knowledge of the value of Φ(n), which is generally unknown to the cryptography algorithm that implements the private operation (signature or decryption).
A variant of that method has therefore been proposed, based not only on the knowledge of the value of Φ(n), but also on the knowledge of the public exponent e. (1) gives us: e·d=1 modulo Φ(n) and so an integer k exists such that: e·d−1=k·Φ(n).
Therefore, the expression x=y(d+r·Φ(n)) modulo n can be computed in the following form:
x=y(d+r·(ed−1)) modulo n, where r is a random integer.
That countermeasure method is thus computationally equivalent to the method from which it follows, but it offers the advantage of not requiring knowledge of the value of Φ(n). It requires less memory in the sense that it does not require Φ(n) to be kept.
However, in order to be implemented, that variant countermeasure requires knowledge of the value of the public exponent e. Unfortunately, in many cryptography applications, the component or the device implementing the private operation of the RSA algorithm does not always have the public exponent e, in particular when it executes the private operation only. Therefore, in that context, the public exponent e is generally unknown or unavailable.
The above-described countermeasures are mainly intended for parrying attacks of the DPA type. However, they also make SPA-type attacks more difficult insofar as the execution of the algorithm is non-deterministic.
As regards the other above-mentioned type of attack, namely the “fault” attack, the best possible protection for parrying it consists in testing, in standard mode, whether the value x obtained by applying the private operation does indeed satisfy the relationship xe=y modulo n of the public operation. If it does not, the value y is not returned, so as to prevent it from being used for cryptanalysis purposes.
In CRT mode, the protection consists in checking firstly whether the relationships xe=y modulo p and xe=y modulo q are indeed satisfied.
When those relationships are satisfied, it is possible to be certain that no errors have occurred during the running of the private operation of the RSA algorithm.
However, a drawback preventing implementation of such checking against fault attacks in standard mode or in CRT mode is that those checking operations also require prior knowledge of the public exponent e. Unfortunately, as explained above, the component or the device implementing the private operation of the RSA algorithm in standard mode or in CRT mode does not always have the public exponent e, in particular when it executes the private operation only. In that context, the public exponent e is therefore generally unknown or unavailable.
To that end, Patent Document FR 2 830 146 (D1) proposes a method making it possible to perform certain steps of a cryptography algorithm, in particular of the RSA type in standard mode or in CRT mode, using a public exponent e that is not known a priori.
The method disclosed in D1 makes it possible, in particular, to provide a countermeasure, especially against fault attacks, that offers the best possible protection as mentioned above, even when the public exponent e is not known.
For that purpose, let (e, d) be a corresponding pair of RSA exponents that are respectively public and private, and let n be the RSA modulus. D1 starts from the following observation that, in 95% of cases, the value of the public exponent e is chosen from among the values 216+1, 3, 17. The method of D1, explained briefly herein with reference to the standard mode but that can equally well be applied to the CRT mode, then consists in checking that e is indeed equal to one of said values by successively testing whether ei·d=1 modulo Φ(n), where ei Φ E={216+1, 3, 17}, until the relationship is satisfied.
When the relationship is satisfied for one ei, then it is known that e=ei. Once the value of the public exponent e has been determined in this way, e is stored with a view to being used in computations of the RSA algorithm aiming to check that no errors have occurred due to a fault attack during the running of a corresponding private operation of the RSA algorithm. Thus, knowing e, it is possible to assert with a probability equal to 1 that the private operation relating, for example, to generating a signature s, where s=μ(m)d modulo n, where μ(m) is the value obtained by applying a padding function μ to the message m to be signed, has been performed without error merely by checking that the value s obtained satisfies the relationship se=μ(m) modulo n of the corresponding public operation.
If it has not been possible to attribute any value of ei to e, it then necessary, in D1, to note that the computations of the RSA algorithm using the value e for securing against fault attacks cannot be performed.
However, a drawback with the method proposed by D1 is that it requires a plurality of modular computations to be performed when successive testing is done to determine whether the relationship eid=1 modulo Φ(n) is satisfied, for a value ei from among the ei values envisaged. That method is thus prohibitive in terms of computation time and of computation resources.
Thus, the problem that arises is to mitigate the above-mentioned drawbacks.